| 翻訳と辞書 |
| Graph cuts in computer vision ： ウィキペディア英語版 |
Graph cuts in computer vision
As applied in the field of computer vision, graph cuts can be employed to efficiently solve a wide variety of low-level computer vision problems (''early vision''〔Adelson, Edward H., and James R. Bergen (1991), "(The plenoptic function and the elements of early vision )", Computational models of visual processing 1.2 (1991).〕), such as image smoothing, the stereo correspondence problem, and many other computer vision problems that can be formulated in terms of energy minimization. Such energy minimization problems can be reduced to instances of the maximum flow problem in a graph (and thus, by the max-flow min-cut theorem, define a minimal cut of the graph). Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the maximum a posteriori estimate of a solution. Although many computer vision algorithms involve cutting a graph (e.g., normalized cuts), the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization (other graph cutting algorithms may be considered as graph partitioning algorithms).
"Binary" problems (such as denoising a binary image) can be solved exactly using this approach; problems where pixels can be labeled with more than two different labels (such as stereo correspondence, or denoising of a grayscale image) cannot be solved exactly, but solutions produced are usually near the global optimum.
== History ==
The theory of graph cuts was first applied in computer vision in the seminal paper by Greig, Porteous and Seheult〔D.M. Greig, B.T. Porteous and A.H. Seheult (1989), ''Exact maximum a posteriori estimation for binary images'', Journal of the Royal Statistical Society Series B, 51, 271–279.〕 of Durham University. In the Bayesian statistical context of smoothing noisy (or corrupted) images, they showed how the maximum a posteriori estimate of a binary image can be obtained ''exactly'' by maximizing the flow through an associated image network, involving the introduction of a ''source'' and ''sink''. The problem was therefore shown to be efficiently solvable. Prior to this result, ''approximate'' techniques such as simulated annealing (as proposed by the Geman brothers〔D. Geman and S. Geman (1984), ''Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images'', IEEE Trans. Pattern Anal. Mach. Intell., 6, 721–741.〕), or iterated conditional modes (a type of greedy algorithm as suggested by Julian Besag)〔J.E. Besag (1986), ''On the statistical analysis of dirty pictures (with discussion)'', Journal of the Royal Statistical Society Series B, 48, 259–302〕 were used to solve such image smoothing problems.
Although the general -colour problem remains unsolved for the approach of Greig, Porteous and Seheult〔 has turned out〔Y. Boykov, O. Veksler and R. Zabih (1998), "(Markov Random Fields with Efficient Approximations )", ''International Conference on Computer Vision and Pattern Recognition (CVPR)''.〕〔Y. Boykov, O. Veksler and R. Zabih (2001), "(Fast approximate energy minimisation via graph cuts )", ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', 29, 1222–1239.〕 to have wide applicability in general computer vision problems. Greig, Porteous and Seheult approaches are often applied iteratively to a sequence of binary problems, usually yielding near optimal solutions.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Graph cuts in computer vision」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|